package com.shuang.stack5;

import java.util.Stack;

class Solution {
    //单调递减栈 栈顶元素是中间值的下标 当前遍历到的是右边第一个比他小的数 左边第一个比它小的数在栈顶的下一个
    //高度就是中间下标对应的高度值 宽度为右边第一个小的下标减去左边第一个小的下标再减1 结果取所有面积的最大值
    //细节方面 需要对数组进行首尾加0操作 尾部加0是防止数组本身是单调递增的一直把所有元素都加到栈里也没有进行计算结果逻辑
    //首部加0 是防止数组本身是单调递减的 第一个元素加的时候第二个元素再加就要开始计算结果逻辑了但是计算结果逻辑需要三个值才可以 此时找不到第三个值 所以先对数组进行首尾加0操作
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<Integer>();

        // 数组扩容，在头和尾各加入一个元素
        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++) {
            newHeights[index + 1] = heights[index];
        }

        heights = newHeights;

        st.push(0);
        int result = 0;
        // 第一个元素已经入栈，从下标1开始
        for (int i = 1; i < heights.length; i++) {
            // 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下标
            if (heights[i] > heights[st.peek()]) {
                st.push(i);
            } else if (heights[i] == heights[st.peek()]) {
                st.pop();
                st.push(i);
            } else {
                while (!st.isEmpty() && heights[i] < heights[st.peek()]) { // 因为进行加0操作了所以判空操作也可以没有
                    int mid = st.pop();
                    if (!st.isEmpty()) {
                        int left = st.peek();
                        int right = i;
                        int w = right - left - 1;
                        int h = heights[mid];
                        result = Math.max(result, w * h);
                    }
                }

                st.push(i);
            }
        }
        
        return result;
    }
}